﻿/* * Write a program that reads an array of integers and removes from it a minimal number of elements in such way that the remaining array is sorted in increasing order. Print the remaining sorted array. Example:
	{6, 1, 4, 3, 0, 3, 6, 4, 5}  {1, 3, 3, 4, 5} */




using System;

class MinimalNumberSort
{
    static void Main()
    {
        uint N;

        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter a positive integer.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);

        iProvided = false; //reset iProvided
        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do
            {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i + 1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }

        /* NE RABOTI - napraveno (t.e. opit) po Longest increasing subsequence algorithm 
         ot wikipedia: http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms 
         problema e che ne izchislqva pravilno j na vsqka iteraciq, ne mojah da go opravq, no ima neshto
         syvsem malko koeto trqbva da se pipne i bi trqbvalo da zaraboti */
        //int L = 0, j = 0, tmp = 0;
        //int[] P = new int[N];
        //int[] M = new int[N];
        //Array.Sort(nums);
        //bool f = false;
       
        //for (int i = 0; i < nums.Length; i++)
        //{
        //    //f = false;
        //    while (j <= L)
        //    {
        //        tmp = Array.BinarySearch(nums, j);
        //        if (tmp >= 0 && (nums[M[j]] < nums[i]))
        //        {
        //            f = true;
        //        }
        //        else f = false;
        //        j++;
        //    }
        //    if (f == false) j = 0;
        //    else j = tmp;
        //    P[i] = M[j];
        //    if (j == L || (nums[i] < nums[M[j + 1]]))
        //    {
        //        M[j + 1] = i;
        //        L = Math.Max(L, j + 1);
        //    }
        //}
        //for (int i = 0; i < P.Length; i++) Console.WriteLine(P[i]);

        int[] indices = new int[nums.Length];
        int[] index = new int[nums.Length];

        string results = null;
        for (int i = nums.Length - 1; i >= 0; i--) results += Combo(nums, index, i, 0, 0);
        //Console.WriteLine(results);
    }

    private static string Combo(int[] nums, int[] index, int k, int i, int next)
    {
        if (i > k) return null;
        string S = null;
        for (int j = next; j < nums.Length; j++)
        {
            index[i] = j;
            
            S = Combo(nums, index, k, i + 1, j + 1);
            if (i == k)
            {
                string c = Check(nums, index, k);
                if (c != null) Console.WriteLine(c);
                break;
            }
        }
        return S;
    }

    private static string Check(int[] nums, int[] index, int k)
    {
        string Str = null;
        for (int i = 0; i < k; i++)
        {
            if (nums[index[i]] > nums[index[i + 1]]) return null;
        }
        for (int i = 0; i <= k; i++)
        {
            if (i != k) Str += nums[index[i]] + " ";
            else Str += nums[index[i]] + ",";
        }
        return Str;
    }
}
